/**
//给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 
//
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 
//
// 你可以按任意顺序返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,7,11,15], target = 9
//输出：[0,1]
//解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,4], target = 6
//输出：[1,2]
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,3], target = 6
//输出：[0,1]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 103 
// -109 <= nums[i] <= 109 
// -109 <= target <= 109 
// 只会存在一个有效答案 
// 
// Related Topics 数组 哈希表 
// 👍 10497 👎 0

*/

package com.xixi.easy;

import java.util.*;

public class ID00001TwoSum {
    public static void main(String[] args) {

        Solution solution = new ID00001TwoSum().new Solution();
    }
    // leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 哈希表法 O(n)
         *
         * @param nums
         * @param target
         * @return
         */

        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; ++i) {
                if (hashtable.containsKey(target - nums[i])) {
                    return new int[]{hashtable.get(target - nums[i]), i};
                }
                hashtable.put(nums[i], i);
            }
            return new int[0];
        }
}
// leetcode submit region end(Prohibit modification and deletion)

    /**
     * 暴力双循环O(n²)
     *     public int[] twoSum(int[] nums, int target) {
     *
     *         int[] resultNum = new int[2];
     *         if(nums.length < 2) return resultNum;
     *
     *         int i = 0;
     *         while(i < nums.length){
     *             int j = i + 1;
     *             while( j < nums.length) {
     *                 if((nums[i] + nums[j]) == target ) {
     *                     resultNum[0] = i;
     *                     resultNum[1] = j;
     *                     return resultNum;
     *                 }else{
     *                     ++j;
     *                 }
     *
     *             }
     *             ++i;
     *         }
     *
     *         return resultNum;
     *     }
     *
     *
     */


    //双指针
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, List<Integer>> posMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> numPosList = new ArrayList<>();
            numPosList.add(i);
            numPosList = posMap.putIfAbsent(nums[i], numPosList);
            if (numPosList != null) {
                numPosList.add(i);
                posMap.put(nums[i], numPosList);
            }
        }

        Arrays.sort(nums);

        int a = 0;
        int b = nums.length - 1;
        while (a < b) {
            int sum = nums[a] + nums[b];
            if (sum == target) {
                if (nums[a] == nums[b]) {
                    List<Integer> numPosList = posMap.get(nums[a]);
                    a = numPosList.get(0);
                    b = numPosList.get(1);

                } else {
                    List<Integer> numPosListA = posMap.get(nums[a]);
                    List<Integer> numPosListB = posMap.get(nums[b]);
                    a = numPosListA.get(0);
                    b = numPosListB.get(0);
                }
                break;
            } else if (sum < target) { //小了就找大的
                a++;
            } else { //大了就找小的
                b--;
            }
        }

        return new int[]{a, b};

    }

}
